package com.myc.subjects.slidingwindow;

import com.myc.subjects.utils.ArrayUtils;

import java.util.*;

/**
 * LeetCode题号：239
 *
 * 滑动窗口的最大值
 *
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回滑动窗口中的最大值。
 *
 * 示例 1：
 * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 输出：[3,3,5,5,6,7]
 * 解释：
 * 滑动窗口的位置                   最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 *
 * 示例 2：
 * 输入：nums = [1], k = 1
 * 输出：[1]
 *
 * 示例 3：
 * 输入：nums = [1,-1], k = 1
 * 输出：[1,-1]
 *
 * 示例 4：
 * 输入：nums = [9,11], k = 2
 * 输出：[11]
 *
 * 示例 5：
 * 输入：nums = [4,-2], k = 2
 * 输出：[4]
 *
 * 提示：
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * 1 <= k <= nums.length
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Huadongchuangkoudezuidazhi {

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        Huadongchuangkoudezuidazhi huadongchuangkoudezuidazhi = new Huadongchuangkoudezuidazhi();
        Integer[] result = Arrays.stream(huadongchuangkoudezuidazhi.maxSlidingWindow4(nums, k)).boxed().toArray(Integer[]::new);
        ArrayUtils.showArray(result);
    }

    /**
     * 方法一：暴力法
     * 时间复杂度：O((n-k)(k-1)) ==> O(kn - k^2 + k)
     * 最直观的，也是很容易能想到的遍历数组，求几个数中的最大值，但是时间复杂度不是很理想，力扣提交超出时间限制。
     * 而且没有使用到滑动窗口的思想
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        //定义结果数组
        int[] result = new int[nums.length - k + 1];

        //遍历数组每一位
        for(int i = 0; i < nums.length - k + 1; i++){

            int max = nums[i];//先定义最大值

            //遍历i位置后面k - 1个数字，找出最大值
            for(int j = i + 1; j < i + k; j++){
                max = Math.max(max, nums[j]);
            }

            result[i] = max;
        }

        return result;
    }

    /**
     * 方法二：大顶堆（优先队列）
     * 时间复杂度:O((n - k + 1) * logk),比方法一要低，但还是超出时间限制
     * 使用大顶堆数据结构来求最大值，也是一种滑动窗口的思想
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];

        //定义大顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;//o2 - o1才是大顶堆，o1 - o2是小顶堆
            }
        });

        for(int i = 0; i < nums.length - k + 1; i++){
            if(i == 0){//i=0时组装大顶堆
                for(int j = 0; j < k; j++){
                    heap.add(nums[j]);
                }
            }else{//像右移动大顶堆（滑动窗口思想）
                heap.remove(nums[i - 1]);
                heap.add(nums[i + k - 1]);
            }
            result[i] = heap.peek();
        }
        return result;
    }

    /**
     * 方法三：双向队列
     * 时间复杂度：O(n)，每个数据都最多只有入队，和出队两个操作
     * 使用双向队列来记录窗口的最大值，这个双向队列很巧妙地保存下了每个窗口可能的最大值。
     * 这也是一种滑动窗口的思想，同时可以将时间复杂度降为O(n)，这样才能满足力扣的题目要求。
     */
    public int[] maxSlidingWindow3(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];

        //定义双向队列来记录滑动窗口的最大值
        Deque<Integer> deque = new ArrayDeque<>();

        //初始化双向队列
        for(int i = 0; i < k; i++){
            while(!deque.isEmpty() && deque.getLast() < nums[i])//这样可以保证双向队列是一个递减序列，第一个值就是窗口最大值
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        result[0] = deque.getFirst();//确认第一个结果

        //开始移动窗口
        for(int i = k; i < nums.length; i++){
            //如果双向队列第一个值是要去掉的那个值，则去掉这个值
            if(deque.getFirst() == nums[i - k]) deque.removeFirst();
            //再移动，找出最大值，因为是递减顺序，所以放心的删吧
            while(!deque.isEmpty() && deque.getLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);

            result[i - k + 1] = deque.getFirst();//注意：这里是第i - k + 1位的结果
        }

        return result;
    }

    /**
     * 方法四：左右扫描
     * 时间复杂度：O(n)
     * 使用了分治思想，也是一种数学方法，我觉得这种方法可遇而不可求，如果想学会那就背吧
     * 步骤；
     * 1.将数组以k为单位长度分成nums.length / k + 1 个部分
     * 2.分别向左向右扫描数组，求出对应位置的最大值，注意以每个部分为界限求最大值，这样就可以得到两个长度也为nums.length的最大值统计数组。
     * 3.则每个窗口的最大值，就等于 左扫描数组相同窗口位置的最右边的值 与 右扫描数组相同窗口位置的最左边的值 此二者中更大的值。
     * 4.将此最大值挨个儿放进结果数组
     */
    public int[] maxSlidingWindow4(int[] nums, int k){
        int[] result = new int[nums.length - k + 1];

        //定义左右扫描结果最大值数组
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];

        //左右扫描数组
        for(int i = 0; i < nums.length; i++){
            //左扫描
            if(i % k == 0) left[i] = nums[i];
            else left[i] = nums[i] > left[i - 1] ? nums[i] : left[i - 1];

            //可以在同一个循环中右扫描数组
            int j = nums.length - i - 1;
            if(j % k == k - 1 || j == nums.length - 1) right[j] = nums[j];//最右边的数必然是一个块的开始
            else right[j] = nums[j] > right[j + 1] ? nums[j] : right[j + 1];
        }

        //每个窗口的最大值，就等于 左扫描数组相同窗口位置的最右边的值 与 右扫描数组相同窗口位置的最左边的值 此二者中更大的值
        for(int i = 0; i < nums.length - k + 1; i++){
            result[i] = Math.max(left[i + k - 1],right[i]);
        }

        return result;
    }

    //官方题解
    //优先队列（大顶堆）
    public int[] maxSlidingWindowOfficial1(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

    //单调队列（这里用的是双向链表）
    public int[] maxSlidingWindowOfficial2(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

    //分块 + 预处理
    public int[] maxSlidingWindowOfficial3(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            }
            else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }
}

/**
 * 总结：
 * 可行题解只有 双向队列 和 左右扫描，大顶堆 和 双向队列 这两种方法是利用特殊数据结构，要能在理解题意的时候想出这些方法
 * 对于左右扫描方法，我觉得还是背一背吧。。。
 * 当然，在同一个循环中镜像左右扫描这个思路值得以后借鉴
 */
